package com.mxw.leetcode.Demo;


import com.mxw.leetcode.C1二叉树.entity.TreeNode;
import com.mxw.leetcode.D1排序.A1归并排序;

import java.util.*;

/**
 * @author miao
 * <p>
 * 全排列
 */
public class Demo1 {


    public static String minWindow(String s, String t) {

        HashMap<Character, Integer> need = new HashMap<>();

        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0;
        int start = 0, len=Integer.MAX_VALUE;

        while (right < s.length()) {
            char c = s.charAt(right);
            if (need.containsKey(c)) {
                need.put(c, need.get(c) - 1);
            }
            right++;

            while (check(need)){
                if (right - left < len) {
                    len = right - left;
                    start = left;
                }
                char c1 = s.charAt(left);
                if (need.containsKey(c1)) {
                    need.put(c1, need.get(c1) + 1);
                }
                left++;
            }
        }

        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

    static private boolean check(HashMap<Character, Integer> map) {

        for (Integer value : map.values()) {
            if (value > 0) {
                return false;
            }
        }
        return true;
    }


}
